The present invention relates to data compression, and more specifically to path compression of a network graph by encoding hops within a path.
Data compression is a technique used ubiquitously across many domains in computing, in order to optimize the storage or network requirements for a given system. In lossless compression, the original message can be perfectly reconstructed (decompressed) from the compressed version of the message. The most commonly used compressors work by removing redundancy in data by exploiting the patterns that appear within it. The extent they can do this is fundamentally limited by the data's predictability; a measure of its entropy. Many domain-specific compression algorithms are in use which make assumptions about the underlying data to improve compression performance. JPEG, GIF, PNG (image compression formats) and MP3, FLAC (audio compression formats) are examples of both lossless and lossy domain-specific algorithms that make such assumptions.
Many analytical problems can be modelled as the interacting nodes of a graph. One of the most common structures of practical use in graph analytics is the path. While graph compression is a very active area of research, and specialized compression techniques have been devised to aid in the storage, transmission and computation of data on a variety of graph problems, known graph compression techniques do not address compression of paths within a graph.
Delta encoding within the context of graphs has been tried, but delta encoding has not been applied so as to incorporate the actual structure (connectivity of nodes) of the graph itself.